package subject_set.top101;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author haomin
 * @date 2022/11/02 20:48
 **/
public class BM30 {
    public class Solution {
        public TreeNode Convert(TreeNode pRootOfTree) {
            if(pRootOfTree == null) return pRootOfTree;
            Deque<TreeNode> s = new LinkedList<>();
            TreeNode cur = pRootOfTree;
            TreeNode pre = null;
            while(!s.isEmpty() || cur != null){
                while(cur != null) {
                    s.push(cur);
                    cur = cur.left;
                }
                cur = s.pop();
                if(pre == null){
                    pRootOfTree = cur;
                }else {
                    pre.right = cur;
                    cur.left = pre;
                }
                pre = cur;
                cur = cur.right;
            }
            return pRootOfTree;
        }
    }
    public class Solution2 {
        TreeNode head = null;
        TreeNode pre = null;
        public TreeNode Convert(TreeNode pRootOfTree) {
            inOrder(pRootOfTree);
            return head;
        }
        private void inOrder(TreeNode root){
            if(root == null) return;
            inOrder(root.left);
            if(head == null){
                head = root;
            }else {
                pre.right = root;
                root.left = pre;
            }
            pre = root;
            inOrder(root.right);
        }
    }

}